Міністерство освіти та науки України Національний університет «Львівська політехніка» Кафедра автоматизованих систем управління / Лабораторна робота №4 з дисципліни «Комп’ютерна графіка» на тему: “Алгоритм Коена-Засерленда” Львів 2014 Лабораторна робота №4 Тема: Алгоритм Коена-Сазерленда Мета роботи: вивчення алгоритму Коена-Сазерленда Теоретичні відомості: Перед тим, як досліджувати методи одержання зображень більш складних, ніж відрізки прямих, розглянемо проблему, присутню в більшості задач комп'ютерної графіки. Ця проблема відсікання зображення за деякою межею, наприклад, по межі екрану, або, в загальному випадку, деякого прямокутного вікна. Розглянемо цю задачу стосовно відрізкам прямих. Деякі з них повністю лежать всередині області екрану, інші цілком поза нею, а деякі перетинають межу екрану. Правильне відображення відрізків означає знаходження точок перетину їх з межею екрану і малювання тільки тих їх частин, які потрапляють на екран. Один з очевидних способів відсікання відрізків полягає у визначенні точок перетину прямої, що містить відрізок, з кожної з чотирьох прямих, на яких лежать межі вікна та перевірки чи не лежить хоча б одна точка перетину на межі. У цьому випадку для кожної пари сторона-відрізок необхідно вирішувати систему з двох рівнянь, використовуючи операції множення і ділення. Якщо зображення виходить за межі екрану, то на частини дисплеїв збільшується час побудови за рахунок того, що зображення будується в "думці". У деяких дисплеях вихід за межі екрану призводить до спотворення картини, так як координати просто обмежуються при досягненні ними граничних значень, а не виконується точний розрахунок координат перетину (ефект "стягування" зображення). Деякі, в основному, прості дисплеї просто не допускають виходу за межі екрану. Все це, особливо в зв'язку з широким використанням технології перегляду вікнами, потребує виконання відсікання сцени по кордонах вікна видимості. У простих графічних системах достатньо двомірного відсікання, в тривимірних пакетах використовується трьох і чотиривимірне відсікання. Останнє виконується в раніше розглянутих однорідних координатах, що дозволяють єдиним чином виконувати аффінні і перспективні перетворення. Програмне виконання відсікання достатньо повільний процес, тому, природно, в потужні дисплеї вбудовується відповідна апаратура. Перше повідомлення про апаратуру відсікання, що використовує алгоритм відсікання діленням відрізка навпіл і реалізованої в пристрої Clipping Divider, з'явилося в 1968 р. Цей алгоритм був розглянутий при вивченні технічних засобів. Тут ми розглянемо програмні реалізації алгоритму відсікання. Відсікаються відрізки можуть бути трьох класів - цілком видимі, цілком невидимі і які перетинають вікно. Очевидно, що доцільно можливо більш рано, без виконання великого обсягу обчислень прийняти рішення про видимості цілком або відкиданні. За способом вибору простого рішення про відкидання невидимого відрізка цілком або прийняття його існує два основних типи алгоритмів відсікання - алгоритми, які використовують кодування кінців відрізка або всього відрізка і алгоритми, які використовують параметричне представлення відсікаються відрізків і вікна відсікання. Представники першого типу алгоритмів - алгоритм Коена-Сазерленда (Cohen-Sutherland, CS-алгоритм) і FC-алгоритм (Fast Clipping - алгоритм). Представники алгоритмів другого типу - алгоритм Кірус-Бека (Curus-Beck, CB - алгоритм) і пізніший алгоритм Ліанга-Барського (Liang-Barsky, LB-алгоритм). Алгоритми з кодуванням застосовні для прямокутного вікна, сторони якого паралельні осях координат, в той час як алгоритми з параметричним представленням застосовні для довільного вікна. Спочатку ми розглянемо алгоритм Коена-Сазерленда, який є стандартом де-факто алгоритму відсікання ліній і володіє одним з кращих швидкодії при компактній реалізації. Потім розглянемо найбільш швидкий, але і надзвичайно громіздкий FC-алгоритм. Далі розглянемо алгоритм Ліанга-Барського для відсікання прямок...